package com.aqie.easy.binarySearchTree;

import com.aqie.easy.structure.BST2;
import com.aqie.easy.structure.TreeNode;

/**
 * 938. 二叉搜索树的范围和
 * 二叉搜索树： 左节点 < 根节点 < 右节点
 * 前序遍历： 根 -> 左 -> 右
 * 中序遍历： 左 -> 根 -> 右
 * 后序遍历： 左 -> 右 -> 根
 */
public class RangeSumBST {
    /**
     * 使用中序遍历
     * @param root
     * @param L
     * @param R
     * @return 区间内 范围和
     */
    public int sum = 0;
    public int rangeSumBST(TreeNode root, int L, int R) {
        if (root != null){
            rangeSumBST(root.left, L, R);
            sum += (root.val >= L && root.val <= R) ? root.val : 0;
            System.out.println(root.val + " sum :" + sum);
            rangeSumBST(root.right, L, R);
            return sum;
        }
        return 0;
    }

    public static void main(String[] args) {
        int[] arr = {10,5,15,3,7,18};
        // int[] arr = {10,5,15,3,7,13,18,1,6};
        BST2 bst2 = new BST2();
        for(int i : arr){
            bst2.add(i);
        }
        // System.out.println(bst2.toString());

        TreeNode node = new TreeNode(10);
        node.right = new TreeNode(15);
        node.left= new TreeNode(5);
        node.left.left= new TreeNode(3);
        node.left.right= new TreeNode(7);
        node.right.right= new TreeNode(18);
        System.out.println(new RangeSumBST().rangeSumBST(node,7,15));

        // 中序遍历
        // BinarySearchUtil.inOrder(node);

    }
}
